/**
 * Created with IntelliJ IDEA.
 * User: user
 * Date: 22.03.13
 * Time: 16:11
 * To change this template use File | Settings | File Templates.
 */
public class GenericQuickSort <T extends Comparable<T>>{

    public T[] getNumbers() {
        return numbers;
    }

    private T[] numbers;
     private int number;

        public void sort(T[] values) {
            // Check for empty or null array
            if (values ==null || values.length==0){
                return;
            }
            this.numbers = values;
            number = values.length;
            quickSort(0, number - 1);
        }

    public void print(){
        for( T obj : numbers){
            System.out.println(obj.toString());
        }
    }

        private void quickSort(int low, int high) {
            int i = low, j = high;
            // Get the pivot element from the middle of the list
            T pivot = numbers[low + (high-low)/2];

            // Divide into two lists
            while (i <= j) {
                // If the current value from the left list is smaller then the pivot
                // element then get the next element from the left list
                while (numbers[i].compareTo(pivot) < 0) {
                    i++;
                }
                // If the current value from the right list is larger then the pivot
                // element then get the next element from the right list
                while (numbers[j].compareTo(pivot) > 0) {
                    j--;
                }

                // If we have found a values in the left list which is larger then
                // the pivot element and if we have found a value in the right list
                // which is smaller then the pivot element then we exchange the
                // values.
                // As we are done we can increase i and j
                if (i <= j) {
                    exchange(i, j);
                    i++;
                    j--;
                }
            }
            // Recursion
            if (low < j)
                quickSort(low, j);
            if (i < high)
                quickSort(i, high);
        }

        private void exchange(int i, int j) {
            T temp = numbers[i];
            numbers[i] = numbers[j];
            numbers[j] = temp;
        }

    public static void main(String[] args) {
        Integer[] arr = {5, 3, 2, 7};
        GenericQuickSort<Integer> quickSort = new GenericQuickSort<Integer>();
        quickSort.sort( arr);
        quickSort.print();

        MyComparableObject[] mA = new MyComparableObject[5];
        mA[0] = new MyComparableObject("c", 1);
        mA[1] = new MyComparableObject("a", 1);
        mA[2] = new MyComparableObject("a", 2);
        mA[3] = new MyComparableObject("a", 0);
        mA[4] = new MyComparableObject("c", 1);
        GenericQuickSort<MyComparableObject> qSort = new GenericQuickSort<MyComparableObject>();
        qSort.sort( mA);
        qSort.print();
    }
}